package com.sh.链表;

import java.util.List;

/**
 * @Auther: sh
 * @Version 1.0
 * @Description:
 */
public class 环形链表 {
    public boolean hasCycle(ListNode head) {

        /**
         * 1、设置快慢指针  快2  慢1
         * 2、如果快追上慢就是有环
         */

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    public ListNode detectCycle(ListNode head) {

        /**
         * 1、设置快慢指针  快2  慢1
         * 2、找到快慢指针交点
         * 3、另起一个指针从头开始
         * 4、和慢指针相交的点就是环起点
         */

        if (head==null || head.next==null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode cur = fast;   // 快慢指针交点
                ListNode res = head;
                while (res != cur) {
                    res = res.next;
                    cur = cur.next;
                }
                return res;
            }
        }
        return null;

    }
}

